﻿using System;

/// <summary>
/// 大顶堆
/// </summary>
/// <typeparam name="T"></typeparam>
internal class Heap<T> where T : IComparable<T> {
	public static void HeapSort(T[] objects) {
		for(int i = objects.Length/2-1;i>=0;--i)
			heapAdjustFromTop(objects,i,objects.Length);
		for(int i = objects.Length-1;i>0;--i) {
			swap(objects,i,0);
			heapAdjustFromTop(objects,0,i);
		}

	}
	public static void heapAdjustFromBottom(T[] objects,int n) {
		while(n>0&&objects[(n-1)>>1].CompareTo(objects[n])<0) {
			swap(objects,n,(n-1)>>1);
			n=(n-1)>>1;
		}
	}
	public static void heapAdjustFromTop(T[] objects,int n,int len) {
		while((n<<1)+1<len) {
			int m = (n<<1)+1;
			if(m+1<len&&objects[m].CompareTo(objects[m+1])<0)
				++m;
			if(objects[n].CompareTo(objects[m])>0) return;
			swap(objects,n,m);
			n=m;
		}
	}
	private static void swap(T[] objects,int a,int b) {
		T tmp = objects[a];
		objects[a]=objects[b];
		objects[b]=tmp;
	}

}

/// <summary>
/// 泛型优先队列，大者先出队
/// </summary>
/// <typeparam name="T">实现IComparable<T>的类型</typeparam>
public class PriorityQueue<T> where T : IComparable<T> {
	private const int defaultCapacity = 0x10;//默认容量为16

	public PriorityQueue() {
		buffer=new T[defaultCapacity];
		heapLength=0;
	}

	public bool Empty() {
		return heapLength==0;
	}

	public T Top() {
		if(heapLength==0) throw new OverflowException("优先队列为空时无法执行返回队首操作");
		return buffer[0];
	}

	public void Push(T obj) {
		if(heapLength==buffer.Length) expand();
		buffer[heapLength]=obj;
		Heap<T>.heapAdjustFromBottom(buffer,heapLength);
		heapLength++;
	}

	public void Pop() {
		if(heapLength==0) throw new OverflowException("优先队列为空时无法执行出队操作");
		--heapLength;
		swap(0,heapLength);
		Heap<T>.heapAdjustFromTop(buffer,0,heapLength);
	}

	private void expand() {
		Array.Resize<T>(ref buffer,buffer.Length*2);
	}

	private void swap(int a,int b) {
		T tmp = buffer[a];
		buffer[a]=buffer[b];
		buffer[b]=tmp;
	}

	private int heapLength;
	private T[] buffer;

}